EVENTO
Complexidade Computacional de Problemas em Convexidade de Grafos
Tipo de evento: Seminário LNCC
Seja G um grafo finito e V(G) o seu conjunto de vértices. Uma convexidade de G é uma família de subconjuntos de vértices de G, contendo V(G), bem como o conjunto vazio, e fechada por interseções.Essa definição, bastante geral, propicia o estudo de diversos casos especiais de convexidades distintas, cada qual com suas características próprias e aplicações. Foram introduzidos, ao longo do tempo, diversos parâmetros comuns a todas essas convexidades distintas. Esses parâmetros possuem aplicações em áreas diversas, tais como, redes sociais, percolação, disseminação de opinião, computação distribuída, etc. Nesta palestra serão examinados aspectos da complexidade computacional dos problemas e algoritmos destinados à computação destes parâmetros. Serão discutidos casos de NP-completude e casos de algoritmos polinomiais.
Data Início: 13/07/2015 Hora: 14:00 Data Fim: Hora: 15:30
Local: LNCC - Laboratório Nacional de Computação Ciêntifica - Auditorio A
Comitê Organizador: Jayme Luiz Szwarcfiter - - -
